package 力扣_树算法.搜索树;


/**236. 二叉树的最近公共祖先
 * @author zx
 * @create 2022-04-16 10:38
 */
public class Num236 {
    /**
     * @return
     * 分析规律：p和q可能有两种分布情况
     * 情况一：p和q分布在了当前根的左子树和右子树上面,此时当前根就是二者的最近公共祖先,递归中可直接返回当前根结点。
     * 情况二：p和q分布在了当前根的某一边的子树上,当前根结点为p和q其中之一也归结为此情况。
     * 递归时,我们想象是递归查找p或者q,如果当前root是p或者q直接返回,如果当前root不是p或者q,那么就像左右递归
     * 主要的递归逻辑是下面的解释：
     * 两个节点都在左子树的情况：假设在左子树遍历到了p,停止遍历该左子树,遍历右子树,如果没q,说明q包含在左子树里,所以返回左子树
     * 两个节点都在右子树的情况：假设在右子树遍历到了p,停止遍历该右子树,遍历左子树,如果没q,说明q包含在右子树里,所以返回右子树
     *
     * 总结：其实这就是一个后序遍历的模型,只不过是每个父节点都会接收子节点的状态(是否含有p、q)并把这个状态往上传递
     * 直到该结点满足祖先节点的条件.这样一想就豁然开朗了.
     *
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //思考难点.定义规则：假设在某一棵子树上先找到了p,则无需继续遍历这棵子树,因为即使这棵子树有q
        //p也一定是q的祖先,也就是它们两个的最近公共祖先.
        if(null == root || root.val == p.val || root.val == q.val){
            return root;
        }
        //按照上述规则,找到root的左子树的最近公共祖先。
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //按照上述规则,找到root的右子树的最近公共祖先。
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //一边找到了,一边没找到,根据上述规则，找到的就是最近公共祖先。
        if(null == left) {//两个都在右子树
            return right;
        }
        if(null == right) {//两个都在左子树里面
            return left;
        }
        //如果在左右子树分别找到了p和q，则说明root是它们两个的最近公共祖先。
        return root;
    }
}
